This invention relates to microprocessors, and more particularly to table-lookup instruction execution.
Compared with reduced instruction set computer (RISC) microprocessors, complex instruction set computer (CISC) processors execute relatively complex instructions, such as multiplies, memory-indirect moves, and register exchanges. However, these CISC instructions are still much less complex that higher-level application program code.
For example, searching a table of file mappings or translations requires execution of many CISC instructions to construct addresses, read from the table, compare or the data read, and to copy results or addresses to registers. When the lookup term is a long string, more CISC instructions are needed to read the string from memory and move it into the microprocessor's general-purpose registers (GPR's) before the string can be compared to table entries. Long strings may require multiple cycles to move and compare fixed-size portions of data.
The parent application disclosed a functional-level instruction-set computing (FLIC) architecture that can execute function-level instructions that are more complex that CISC instructions. The FLIC architecture also could access variable-length operands using an execution buffer accessible from the processor's execution pipeline. Pointers in the fixed-width GPR's point to variable-length operands in the execution buffer. Execution resources in the processor's pipeline can directly access the variable-length operands in the execution buffer.
One of the FLIC instructions that can be natively executed on the FLIC architecture is a lookup instruction. The lookup instruction causes the processor pipeline to perform many sub-tasks, such as reading and processing a variable-length string to generate a lookup key, generating addresses to read the lookup table, comparing table entries to the key, and writing addresses for matching entries to the registers.
FIG. 1 shows a lookup instruction. Lookup instruction 10 has a width of 32 bits (four bytes) and can be decoded by an instruction decoder for a FLIC processor. Execution of lookup instruction 10 is native, since lookup instruction 10 is not recompiled or translated into many machine-level instructions; lookup instruction 10 is a machine-level instruction.
Lookup instruction 10 contains opcode 12, which is a multi-bit binary number that indicates the type of operation performed by instruction 10. Other native instructions have other binary numbers in the opcode field. Opcode 12 is decoded by the processor's instruction decoder to determine what operation to perform, and perhaps to select a micro-routine of micro code or a sequence of cycles and control signals in a hardware or firmware sequencer.
Opcode 12 is an 8-bit code in this example, allowing for as many as 256 different instruction types to be decoded, such as branches, compares, moves, read/write, input/output, adds, multiplies, divides, etc. Flavor 14 contains a 6-bit binary number that selects a variant or “flavor” of the lookup instruction. For example, one flavor returns the address of a match in the table, another flavor invalidates a matching entry, another allocates a new entry on a miss, other flavors copy data. Flavor 14 is decoded by the instruction decoder to determine the variation of the basic lookup operation to be performed.
The lookup table or cache can be sub-divided into several sub-caches called sections. Different kinds of translations can be stored in the different sections. Section field 16 contains a 3-bit section number that selects one of up to 8 sections in the lookup cache.
Operands are specified by operand fields 20, 22, 24. The input operands are specified by registers M and N while the output result is placed in register R. Operand fields 20, 22, 24 are each 5-bit fields, each selecting one register from among 32 registers in the processor's GPR's.
The user or programmer can perform a cache lookup by including a lookup instruction in the assembly or machine code. The programmer or the code complied by a compiler program specifies the lookup instruction's opcode and flavor code, and the section number of the cache to be searched. The register codes are appended to generate the 32-bit instruction. The FLIC processor decodes this 32-bit instruction and has the execution pipeline execute the lookup instruction routing data to and from the specified registers or locations specified by the registers.